package _interview100;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 239. 滑动窗口最大值
 */
public class No239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            if (i >= k) {
                ans[i - k] = deque.peekFirst();
                if (deque.peekFirst() == nums[i - k]) deque.pollFirst();
            }
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) deque.pollLast();
            deque.addLast(nums[i]);
        }
        ans[n - k] = deque.peekFirst();

        return ans;
    }
}
